1. Field of the Invention
The present invention relates to the field of computer program code performance tuning and more particularly to data splitting of data structures in a computer program.
2. Description of the Related Art
Software development has evolved over time from direct specification of a sequence of processor instructions, to the interpretation of high level source code into a sequence of processor instructions, to the compilation of high level source code into a sequence of processor instructions, to the compilation of high level source code into interpretable intermediate code able to be interpreted at run-time into a sequence of processor instructions. Initial software development focused on the delivery of functionality of code irrespective of the performance of the code at execution time. Over time, however, the complexity of software compels strong consideration of the performance implications of design choices in software development.
To address performance considerations in software development, software developers often performance tune program code. Performance tuning not only involves the optimized choice of operative structures such as looping constructs, but also performance tuning relates directly to the selection and arrangement of data structures in order to optimize memory access. In particular, performance tuning of data structures in program code often involves the consideration of the optimal utilization of cache memory when executing program code. The use of aggregate data types like arrays within program code can directly impact the optimal utilization of cache memory.
In an aggregate data type, it tends to be the case that frequently accessed fields are placed adjacent to sparingly accessed fields mostly due to the style of programming in which the structure of an aggregate data type intends to impart semantic meaning to the reader as opposed to optimal performance of the data type once compiled for execution. Placing frequently accessed fields adjacent to sparingly accessed fields in an aggregate data type, however, can detract from memory performance because the sparingly accessed fields—often referred to as “cold fields”—pollute the data cache and waste memory bandwidth at the expense of the frequently access fields, commonly referred to as the “hot fields”.
Data splitting represents one approach to the remediation of the problem of cache pollution and memory bandwidth waste due to the structuring of an aggregate data type. Contemporary data splitting strategies include affinity-based splitting, frequency-based splitting and maximal splitting. Affinity-based splitting groups fields according to the reference affinity between these fields. Therefore, only fields that are tend to be accessed together at runtime are placed into the same data structure. Frequency-based splitting, by comparison, splits a data structure into two, one of which holds the hot fields and the other one of which hosts the cold fields. Finally, maximal splitting splits each field of a data structure into a separate new data structure. For an array type data structure, each data structure field is stored in an independent array after splitting. Studies show the maximal splitting technique to be the most effective of the foregoing techniques.
Contemporary splitting techniques generate a base array which takes the role of the original array before the transformation. Fields that are not held by the base array are referred to as satellite fields and form the satellite arrays. To access the satellite fields in the program, extra instructions are inserted into the program code to calculate the address of the satellite field. Consequently, the overhead of accessing the satellite fields can become a serious performance problem when the satellite fields are frequently accessed at runtime.
Existing data splitting technologies suffer important drawbacks. First, existing splitting technologies only handle array of structures and do not handle recursive data structures such as linked lists, trees, graphs. Recursive data structures, however, are known to be popular in many programs. Second, the addressing method of existing data splitting technology is known to be inefficient and can result in a significant increase in the number of runtime instructions.